import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author 909584 演示打印1-100的素数的方法
 */
public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// suShu(); //判断素数
		// multiple9X9(); //99乘法表
		// huiWen(); // 判断回形文
		
		int[] arr = { 3, 5, 4, 1, 8, 11, 9};
		 maoPao(arr); // 冒泡排序

		// *** 插入排序法START *****
		// ArrayList<Integer> input = new ArrayList<Integer>();
		// Scanner reader = new Scanner(System.in);
		// System.out.println("reader create");
		// // 输入的时候要在末尾添加一个非整形数字，可以是字符，才能成功跳出循环
		// while (reader.hasNextInt()) {
		// int n = reader.nextInt();
		// input.add(n);
		// }
		//
		// int[] arr = { 3, 5, 4, 1, 8, 11, 9};
		// addInput(arr, input);
		// *** 插入排序法END *****

		// *** 快速排序法START ***
		// int[] waitArr = { 5, 9, 8, 4, 7, 6, 13, 10, 3 };
		// printArr(waitArr);
		// fastSort(waitArr, 0, waitArr.length - 1);
		// *** 快速排序法END *****

		// ticket(); // 售票模式
	}

	/**
	 * 快速排序法，从一个基准点开始，先从最右开始比较，把比基准小的第一个数和基准对换 然后从最左比较，把比基准大的第一个数和基准对换
	 * 
	 * @param waitArr
	 * @param low
	 *            传入需要排序的子数组在原数组中的起始位
	 * @param high
	 *            传入需要排序的子数组在原数组中的结束位
	 */
	private static void fastSort(int[] waitArr, int low, int high) {
		// TODO Auto-generated method stub
		if (low >= high) {
			return;
		}

		if (low == high - 1) {
			if (waitArr[low] > waitArr[high]) {
				swap(waitArr, low, high);
			}
			return;
		}

		int left = low;
		int right = waitArr.length - 1;
		int point = low;
		int num = waitArr[point];

		// 一次排序的判断标识为left=right - 1
		while (left < right - 1) {
			// 从右边开始比较，找到比基准要小的第一个数，与基准数调换位置
			while (num < waitArr[right] && right > low) {
				right--;
			}
			swap(waitArr, right, point);
			point = right;

			// 第二次从左边开始比较，找到比基准要大的第一个数，与基准数调换位置
			while (num > waitArr[left] && left < high) {
				left++;
			}
			swap(waitArr, left, point);
			point = left;

		}

		printArr(waitArr);

		System.out.println("low = " + low + " point = " + point + " high = "
				+ high + " size = " + waitArr.length);
		// 再次比较的数列不能再包含point指向的数字了，因为point指向的数已经在数组中排好了位置，
		// 如果还有包含它，那么在两个子数组中一定会有一边的比较是没有意义的
		fastSort(waitArr, low, point - 1);
		fastSort(waitArr, point + 1, high);
	}

	/**
	 * 在目标数组中交换两个数
	 * 
	 * @param waitArr
	 * @param point
	 * @param right
	 */
	private static void swap(int[] waitArr, int point, int right) {
		// TODO Auto-generated method stub
		int temp = 0;
		temp = waitArr[right];
		waitArr[right] = waitArr[point];
		waitArr[point] = temp;
	}

	/**
	 * 插入排序法，把第一个数理解成排好序的数组，再比较第二个数进行插入
	 * 
	 * @param arr
	 */
	private static void charu(int[] arr) {
		// TODO Auto-generated method stub
		int temp = 0;
		// int target = 5;
		for (int i = 1; i < arr.length; i++) {

			for (int j = 0; j < i; j++) {
				if (arr[j] > arr[i]) {
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				} else {

				}
			}

			printArr(arr);
		}

	}

	/**
	 * 把输入的数添加进数组
	 * 
	 * @param arr
	 * @param input
	 */
	private static void addInput(int[] arr, int input) {
		// TODO Auto-generated method stub
		int length = arr.length + 1;
		int[] updateArr = new int[length];
		for (int i = 0; i < arr.length; i++) {
			updateArr[i] = arr[i];
		}
		updateArr[length - 1] = input;

		charu(updateArr);
	}

	/**
	 * 方法的重载，把一个数组添加到另一个数组中，然后插入排序
	 * 
	 * @param arr
	 * @param input
	 */
	private static void addInput(int[] arr, ArrayList<Integer> input) {
		// TODO Auto-generated method stub
		System.out.println("create new int[]");

		ArrayList<Integer> updateArr = new ArrayList<Integer>();
		for (int i = 0; i < arr.length; i++) {
			updateArr.add(arr[i]);
		}
		updateArr.addAll(input);

		int length = updateArr.size();
		int[] update = new int[length];
		for (int i = 0; i < length; i++) {
			update[i] = updateArr.get(i);
		}

		charu(update);

	}

	private static void printArr(ArrayList<Integer> arr) {
		// TODO Auto-generated method stub
		for (int i = 0; i < arr.size(); i++) {
			System.out.println(arr.get(i));
		}
		System.out.println();
	}

	private static void printArr(int[] arr) {
		// TODO Auto-generated method stub
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
		System.out.println();
	}

	private static void ticket() {

		/*
		 * TicketThread mt1=new TicketThread(); TicketThread mt2=new
		 * TicketThread(); TicketThread mt3=new TicketThread();
		 * mt1.start();//每个线程都各卖了10张，共卖了30张票 mt2.start();//但实际只有10张票，每个线程都卖自己的票
		 * mt3.start();//没有达到资源共享
		 */

		TicketRunable mt = new TicketRunable();
		Thread A = new Thread(mt);
		A.setName("Thread A");
		Thread B = new Thread(mt);
		B.setName("Thread B");

		B.start();
		A.start();
	}

	/**
	 * 冒泡排序法,利用双循环，每次循环都能找到数组中最大的数或最小的数(看是升序还是降序),所以每次就能少比较一个数
	 * @param arr 
	 */

	private static void maoPao(int[] arr) {

		// *** 读取键盘的输入 START***
		// 方法一
		// List<Integer> origin = new ArrayList<Integer>();
		//
		// Scanner reader = new Scanner(System.in);
		// System.out.println("刚刚输入: " + reader.hasNext());
		// int i = 0;
		// while (true) {
		// int n = reader.nextInt();
		// if (n == 0) {
		// break;
		// }
		// origin.add(n);
		//
		// }
		//
		// for (int j = 0; j < origin.size(); j++) {
		// System.out.print(origin.get(j) + "  ");
		// }
		// 方法二
		// BufferedReader buffer = new BufferedReader(new InputStreamReader(
		// System.in));
		// System.out.println("请输入一串字符串");
		// String text = new String();
		// try {
		// text = buffer.readLine();
		// } catch (IOException e) {
		// // TODO Auto-generated catch block
		// e.printStackTrace();
		// }
		//
		// System.out.println("您输入的字符串是:");
		// String[] s = text.split(" ");
		// for (int i = 0; i < s.length; i++) {
		// origin.add(Integer.parseInt(s[i]));
		// System.out.print(origin.get(i) + "  ");
		// }
		// *** 读取键盘的输入 END***
		
		// 外层循环，每次找到最大或最小的值,然后递增找第二大或第二小的值
		for (int i = 0; i < arr.length - 1; i++) {
			// 找到最大或最小的值放到队伍末尾
			for (int j = 0; j < arr.length - i - 1; j++) {

				if (arr[i] > arr[i + 1]) {
					int temp = 0;
					temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
					printArr(arr);
				}

			}

		}
		System.out.println("结尾：");
		printArr(arr);

	}

	/**
	 * 判断是否是回形数，12321 把每个位置的数字读取出来，颠倒顺序
	 */
	private static void huiWen() {
		// TODO Auto-generated method stub
		for (int i = 10; i < 10000; i++) {
			if (isHui(i)) {
				System.out.println(i);
			}

		}
	}

	/**
	 * 判断一个数是不是回形 假如num = 123,第一次循环得到3，把num除以10得到12
	 * 第二次循环就得到2，把3乘以10，再加上2，得到32，把num再除以10得到1 第三次循环把32乘以10，加上1，就得到了321
	 */
	private static boolean isHui(int i) {
		// TODO Auto-generated method stub
		int result = 0;
		int num = i;
		while (num > 0) {
			// 给上一次的结果乘以10，空出最后的一位填入余数
			result = result * 10 + num % 10;
			// 把num除以10，得到新的数
			num = num / 10;
		}

		if (result == i) {
			return true;
		} else {
			return false;
		}
	}

	/**
	 * 99 乘法表 用一个循环完成两个循环的事情, 以j为判定依据，i每次加1，直到i=j的时候，再把i重置
	 */
	private static void multiple9X9() {
		// TODO Auto-generated method stub

		for (int i = 1, j = 1; j <= 9; i++) {

			System.out.println(i + "X" + j + "=" + i * j);

			if (i == j) {
				i = 0;
				j++;
				System.out.println();
			}

		}
	}

	/**
	 * 判断素数
	 */
	private static void suShu() {
		// TODO Auto-generated method stub
		for (int i = 0; i < 100; i++) {
			if (isPrime(i)) {
				System.out.println("i = " + i);
			}
		}
	}

	/**
	 * 判断i是否为素数，大于i的开根号也是无法除尽的，只需要循环到开根号
	 * 
	 * @return
	 */
	private static boolean isPrime(int i) {
		long sqrt = (long) Math.sqrt(i);
		for (int j = 2; j < sqrt; j++) {
			if (i % j == 0) {
				return false;
			}
		}

		return true;
	}

}
